﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace CodeTop.复习九月份
{
    public class Solution129
    {
        public int SumNumbers1(TreeNode root)//迭代
        {
            int sum = 0;
            Stack<TreeNode> s = new Stack<TreeNode>();
            IList<int> path = new List<int>();

            while (s.Count>0||root != null)
            {

                while (root!=null)
                {
                    s.Push(root);
                    path.Add(root.val); 
                    root = root.left;
                   

                }
                //遇到叶子，收集结果
              int curnum=  ListToNum(path);
                Console.WriteLine("curnum:  "+ curnum);
                sum += curnum;


                path.RemoveAt(path.Count-1);
                root = s.Pop();
                root = root.right;





            }
            return sum;
            

        }

        private int ListToNum(IList<int> path)
        {
            int pre = 0;
            for (int i = 0; i < path.Count; i++)
            {
                pre = pre * 10 + path[i];

            }
            return pre;


        }
        IList<int> res= new List<int>();
        public int SumNumbers(TreeNode root)//递归
        {
           return DFS(root, 0);
            //int sum = 0;
            //for (int i = 0; i < res.Count; i++)
            //{
            //    sum += res[i];
            //}
            //return sum/2;
           
        
        }

        private int DFS(TreeNode root,int pre)
        {
            if (root == null) { 
         return 0;//空节点
            
            } 

          int   sum=pre * 10+root.val ;

            if(root.left==null && root.right == null){

                return sum;//叶子节点
            }else {


             return   DFS(root.left, sum)+    DFS(root.right, sum);//直接计算总和
            }
           


        }
    }
    class Program129
    {

        

        static void Main129(string[] args)
        {

            int[] preorder = [4, 9, 5, 1,0];
            int[] inorder = [5, 9, 1, 4,0];
            Solution105 solution = new Solution105();
            TreeNode root = solution.BuildTree(preorder, inorder);
            //Solution102 LevelOrder = new Solution102();
            //IList<IList<int>> res = LevelOrder.LevelOrder(root);
            //for (int i = 0; i < res.Count; i++)
            //{
            //    for (int j = 0; j < res[i].Count; j++)
            //    {


            //        Console.Write(res[i][j] + ",");
            //    }
            //    Console.WriteLine();
            //}


            Solution129 s = new Solution129();
          int res=  s.SumNumbers(root);
            Console.WriteLine(res);

        }
    }

}
